import java.util.ArrayList;
import java.util.List;

/**
 * 1689. 十-二进制数的最少数目
 * https://leetcode-cn.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/
 */
public class Solutions_1689 {
    public static void main(String[] args) {
        String n1 = "32";  // output: 3
        String n2 = "82734";  // output: 8
        String n3 = "27346209830709182346";  // output: 9

        List<String> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);

        for (String input : inputs) {
            int result = minPartitions(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：找字符串 n 中的最大字符
     * 题目要求：找到和为 n 的 十-二进制数 的最少数目，且 十-二进制数就是只有 1 和 0 数字的数
     * 那么贪心思想：尽可能多得用数字 1
     */
    public static int minPartitions(String n) {
        char[] arr = n.toCharArray();
        char max = '0';
        for (char c : arr) {
            if (c > max) {
                max = c;
            }
        }
        return max - '0';
    }
}
